// Created by WXX on 2021/10/23 15:15
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
 * 内存消耗：5.8 MB, 在所有 C++ 提交中击败了58.24%的用户
 */
class Solution {
public:
    int mySqrt(int x) {

        int l = 0, r = x;
        while (l < r) {
            int mid = l + 1ll + r >> 1;  // 防止越界
            if (mid <= x / mid) l = mid;  // 防止越界
            else r = mid - 1;
        }
        return r;
    }
};

int main() {

    cout << Solution().mySqrt(5) << endl;

    return 0;
}
